# 给你一个链表的头节点 head ，判断链表中是否有环。 
# 
#  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到
# 链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 
# 
#  如果链表中存在环 ，则返回 true 。 否则，返回 false 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入：head = [3,2,0,-4], pos = 1
# 输出：true
# 解释：链表中有一个环，其尾部连接到第二个节点。
#  
# 
#  示例 2： 
# 
#  
# 
#  
# 输入：head = [1,2], pos = 0
# 输出：true
# 解释：链表中有一个环，其尾部连接到第一个节点。
#  
# 
#  示例 3： 
# 
#  
# 
#  
# 输入：head = [1], pos = -1
# 输出：false
# 解释：链表中没有环。
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点的数目范围是 [0, 10⁴] 
#  -10⁵ <= Node.val <= 10⁵ 
#  pos 为 -1 或者链表中的一个 有效索引 。 
#  
# 
#  
# 
#  进阶：你能用 O(1)（即，常量）内存解决此问题吗？ 
# 
#  Related Topics 哈希表 链表 双指针 👍 2250 👎 0
from typing import Optional

from LeetCode.Test.LinkTool import ListNode, LinkedListTool, Link


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        """
        方法一：节点地址存入哈希，判断节点之前是否出现过
        :param head:
        :return:

        dummy = ListNode(-1)
        dummy.next = head
        curr = dummy
        address = set()
        while curr:
            node_id = id(curr)
            if node_id in address:
                return True
            else:
                address.add(node_id)
            curr = curr.next
        return False
        """
        """
        方法二：快慢指针。快指针一次走两步，慢指针一次走一步。如果存在环，则一定会相遇
        :param head: 
        :return: 
        """
        if not head or not head.next:
            return False
        slow = head
        # 如果我们令fast = head。那么两个指针不满足while循环的条件，则循环不会被执行
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

# leetcode submit region end(Prohibit modification and deletion)
link = LinkedListTool([1, 4, 3, 2, 5, 2])
cur = link
for _ in range(2):
    cur = cur.next
i = link
for _ in range(5):
    i = i.next
i.next = cur

print(Solution().hasCycle(link))
